package leetcode

import "container/heap"

func connectSticks(sticks []int) int {
	minHeap := &MinHead{}
	for _, stick := range sticks {
		heap.Push(minHeap, stick)
	}

	totalCost := 0
	for minHeap.Len() > 1 {
		stick1 := heap.Pop(minHeap).(int)
		stick2 := heap.Pop(minHeap).(int)
		totalCost += stick1 + stick2
		heap.Push(minHeap, stick1+stick2)
	}

	return totalCost
}

type MinHead []int

func (h MinHead) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h MinHead) Len() int {
	return len(h)
}

func (h MinHead) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHead) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *MinHead) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}
